package gold.digger;

import gold.utils.InputUtil;

import java.awt.*;
import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC336 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public List<List<Integer>> palindromePairs(String[] words) {
            List<List<Integer>> res = new ArrayList<>();
            Set<Point> resPoint = new HashSet<>();
            Map<String, Integer> map = new HashMap<>();
            for (int i = 0; i < words.length; i++) {
                map.put(words[i], i);
            }

            for (int i = 0; i < words.length; i++) {
                String word = words[i];
                List<String> preList = getPrePalindrome(word), afterList = getAfterPalindrome(word);
                for (String pre : preList) {
                    if (map.containsKey(pre)) {
                        if (map.get(pre) == i) continue;
                        resPoint.add(new Point(map.get(pre), i));
                    }
                }

                for (String after : afterList) {
                    if (map.containsKey(after)) {
                        if (map.get(after) == i) continue;
                        resPoint.add(new Point(i, map.get(after)));
                    }
                }
            }

            for (Point point : resPoint) {
                List<Integer> plist = new ArrayList<Integer>();
                plist.add(point.x);
                plist.add(point.y);
                res.add(plist);
            }

            return res;
        }

        public List<String> getPrePalindrome(String word) {
            List<String> preList = new ArrayList<>();
            for (int i = word.length(); i >= 0; i--) {
                if (!isPalindrome(word.substring(0, word.length() - i))) continue;
                StringBuilder sb = new StringBuilder();
                for (int j = word.length() - 1; j >= (word.length() - i); j--) {
                    sb.append(String.valueOf(word.charAt(j)));
                }
                preList.add(sb.toString());
            }

            return preList;
        }

        public List<String> getAfterPalindrome(String word) {
            List<String> afterList = new ArrayList<>();
            for (int i = word.length(); i >= 0; i--) {
                if (!isPalindrome(word.substring(i, word.length()))) continue;
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < i; j++) {
                    sb.insert(0, String.valueOf(word.charAt(j)));
                }
                afterList.add(sb.toString());
            }

            return afterList;
        }

        public boolean isPalindrome(String str) {
            if (null == str || str.length() <= 1) return true;
            int i = 0, j = str.length() - 1;
            while (i < j) {
                char chi = str.charAt(i++), chj = str.charAt(j--);
                if (chi != chj) return false;
            }

            return true;
        }
    }

    public void run() {
        Solution solution = new Solution();
        String[] arr = InputUtil.toStringArray("[\"a\",\"\"]");
        System.out.println(solution.palindromePairs(arr));
//        System.out.println(solution.getPrePalindrome("a"));
    }

    public static void main(String[] args) throws Exception {
        LC336 an = new LC336();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
